1. Field of the Invention
The present invention relates to a method of coding image data, and more particularly, to a method of coding image data of region of interest using a SPIHT (Set Partional in Hierarchical Tree) algorithm to facilitate compressing and restoring image data of the region of interest.
2. Description of the Related Art
As computer communication and image communication technique has been developed, still image coding compression and transfer technique has also been developed and employed for the communication technique. JPEG (Joint Photographic Coding Experts Group) is generally used as a standard of still image compression coding method. The conventional JPEG employs a compression method based on DCT (Discrete Cosine Transform).
Recently, as a coding method for compressing image data, a wavelet transform coding method is widely used. Data of a wavelet-transformed image is expressed with wavelet coefficients. Methods for performing a compression coding using the characteristics of the wavelet coefficients includes EZW (Embedded Zero-tree Wavelet), SPIHT, TCQ (Trellis Coded Quantization), etc. In the SPIHT algorithm provided by Said and Pearlman, distortion of a restored image is decreased by transforming image data into wavelet domain and gradually transferring the wavelet coefficients.
In a method for transferring important information first, a coefficient having a larger size is first transferred using the fact that the largest coefficient has the largest information amount. In another method for transferring important information first, a bit plane corresponding to the MSB (Most Significant Bit) is first transferred. The bit plane is gradually transferred based on the sequence of significance by transforming an image into wavelet coefficients and sorting the wavelet coefficients based on the size of the same. The key point of the above algorithm is directed to sorting the wavelet coefficients based on the size and effectively storing the sorted information. A detail description of the algorithm follows.
It is first determined whether a certain coefficient (Ci,j) is larger than a predetermined threshold value (2n) This is called “significance test”. In the significance test, if the coefficient (Ci,j) is larger than the threshold value (2n), it is defined as a significant pixel. A hierarchical tree structure is introduced for grouping and expressing insignificant coefficients. As shown in FIG. 1, a hierarchical tree structure is generated when dividing an image signal into four bands based on a recursive method.
FIG. 1 is a view illustrating a case that an image signal is twice transformed into wavelet coefficients. The wavelet coefficients are partitioned based on a hierarchical set having a tree structure. Here, the following sets of coordinates are used.
O(i,j): a set of direct descendant coordinates of coordinate (i,j) and has a circle of {(2i,2j), (2i,2j+1), (2i+1,2j), (2i+1,2j+1)} except for a pyramid structure having a highest and/or lowest value.
D(i,j) a set of all descendant coordinates of coordinate (i,j).
L(i,j)=D(i,j)−O(i,j)
As shown in FIG. 1, four direct descendants exist in one coordinate. Mark “X” of the left upper portion represents a coefficient which does not have a descendant among the coefficients in the highest stage. In addition, the SPIHT algorithm manages coordinates of the coefficients using three lists, such as LSP (List of significant pixel), LIP (List of insignificant pixel) and LIS (List of insignificant set). The LIS represents a list of insignificant coefficient set, the LIP represents a list of insignificant coefficients, and LSP represents a list of significant coefficients.
The SPIHT algorithm has two major stages, a sorting pass and a refinement pass. In the sorting pass, a coefficient is compared with a certain threshold value to compute a significant or insignificant value. In the refinement pass, a coefficient value obtained in the sorting pass is refined. The sorting pass includes a node test for testing significance with respect to the coefficients of the LIP, and a descendent test for testing significance with respect to the entry of an LIS. When a coefficient in the LIP passes the significance test, the coefficient is joined in the LSP. When the entry of the LIS passes the significance test, the entry of the same is divided into coefficients and sets smaller than the entry. All coefficients are sorted based on each bit plane using the obtained threshold values.
Input and output occur at each of the above processes. One bit is generated in every significance test. When one coefficient enters the LSP, one bit related to the coding of the coefficient is generated. Namely, when the threshold value is determined, the bits as many as the number of the LIP entries and the number of the LIS entries are generated in the significance tests. In addition, the bits as many as the number of the LSP entries are generated. In addition, the bits as many as the number of the coefficients which enter into the LSP in the determined threshold value are generated.
In order to decrease the amount of the bits generated in the sorting process, the number of the entries of the LIP and LIS should be decreased. The entry of the LIP represents one coefficient, and the entry included in the LIS represents a set of the coefficients. The entry of the LIS includes four coefficients or coefficients as many as the sum of the multiplier of four. When the entry of the LIS is divided, the coefficients can be divided into significant coefficients, insignificant coefficients and a set of insignificant coefficients. In each list, the number of the entries is increased. Therefore, it is possible to decrease the amount of the generated bits by not separating the entries of the LIS.
As a condition for dividing a set of the insignificant coefficients, if a neighboring coefficient is a significant coefficient or if there is a significant coefficient in a descendent level, the coefficients except for the significant coefficients are entered into the LIP or LIS.
The SPIHT algorithm is well disclosed in an article “A new, fast, and efficient image coded based on set partitioning in hierarchical trees,” by A. Said and W. A. Pearlman, IEEE Trans, Circuits and Systems for Video Technology, Vol. 6, pp. 243–250, June, 1996.”
The coding of region of interest is directed to a method for allocating more bits to a region of interest and transferring information concerning the region of interest first and/or more.
In order to perform coding of region of interest, a region of interest should be first defined. There are two methods for defining a region of interest. In a first method, a region of interest is set in an encoder, and then the region of interest is coded by the encoder. In this case, information concerning the region of interest should be transferred to a decoder. In a second method, after receiving a bit stream transferred from the encoder, a decoder designates a region of interest, and the information of the region of interest is returned to the encoder. Then, the encoder performs a coding operation of the region of interest. In this case, the encoder and the decoder have the information concerning the region of interest. The conventional method for coding the region of interest is shown in FIG. 2.
FIGS. 2A and 2B are views for explaining a conventional region of interest coding method, which show before and after the region of interests is determined, respectively. Here, the horizontal axis represents sorted wavelet coefficients, and the vertical axis represents bit planes of coefficients.
As shown in FIG. 2A, before the region of interest is determined, wavelet coefficients with respect to the entire image are compressed and transferred according to the bit plane. As shown in FIG. 2B, after the region of interest is determined, the coefficients in the region of interest are bit-shifted behind the bit stream compressed with respect to the wavelet coefficients in which the coding is completed before the region of interest is set. The coefficients that are not related to the region of interest are not shifted. Then, the image is entirely coded. The method for compressing the entire image based on the bit shift with respect to the coefficients for the region of interest is well disclosed in an article “Lossy/lossless region-of-interest image coding based on set partitioning in hierarchical trees,” by E. Atsumi and N. Farvardin, IEEE International Conference on Image Processing (ICAP-98), Oct. 4˜7, 1998 Chicago, Ill., USA.”